package com.example.question.list.list1;

/**
 * @Date 2023-07-04
 * @Author Jonathan
 * @link {<a href="https://leetcode.cn/problems/linked-list-cycle-ii/">...</a>}
 * 寻找第一个入环的节点
 */
public class Code09_142 {
    public static void main(String[] args) {
        Code09_142 code = new Code09_142();
    }

    /**
     * todo
     *
     * @param head
     * @return
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        if (head == null || head.next == null) {
            return null;
        }
        if (fast.next.next == slow) {
            return slow;
        }
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                ListNode p = head;
                while (p != slow) {
                    slow = slow.next;
                    p = p.next;
                }
                return p;
            }
        }
        return null;
    }
}
